// ALERT: 此代码中涉及到的链表，默认都带头结点。

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

// FUNCTION: 定义链表结点结构
typedef struct LNode {
	ElemType data;
	// 指向下一个结点
	struct LNode *next;
} LNode, *LinkList;


// FUNCTION: 头插法新建链表
void CreatList_fromHead(LinkList &L) {
	// NOTE: 变量声明
	// STEP: 声明一个结构体指针变量*s，用于存储程序临时申请的内存空间始址。
	LNode *s;

	// STEP: 声明一个整型变量x，用于接收用户输入。（以9999作为最后一个有效数据）
	int x;


	// NOTE: 初始化链表
	// STEP: 创建头结点，并用头指针L指向
	L = (LinkList) malloc(sizeof(LNode));

	// STEP: 初始化头结点
	L->next = NULL;


	// NOTE: 头插法，建立链表
	do {
		// STEP: 从标准输入读取用户输入
		printf("Please input: ");
		scanf("%d", &x);

		// STEP: 创建新节点
		// 申请一个新空间给s，强制类型转换为LNode类型
		s = (LNode *) malloc(sizeof(LNode));
		// 新结点的数据域，初始化为读取到的值
		s->data = x;
		// 新结点的指针域，初始化为空
		s->next = NULL;

		// STEP: 让新结点的指针域，指向链表的第一个元素——链表开始起的第二个结点（即：头结点后面那个结点）
		s->next = L->next;

		// STEP: 更新头结点指针域，让s作为第一个元素
		L->next = s;
	} while (x != 9999); // 直到用户输入9999为止

	printf("ALL CLEAR!\n");

	// HINT: 因为L为引用类型，所以没必要最后返回L！
	// return L;
}


// FUNCTION: 尾插法新建链表
void CreatList_fromTail(LinkList &L) {
	// NOTE: 变量声明
	// STEP: 声明一个结构体指针变量*s和*r。前者用于存储程序临时申请的内存空间始址，后者用于存储链表表尾结点地址。
	// ALERT: 此处有严重理解错误！在创建头结点之前，程序传入的DL是结构类型的空指针。所以，此时用DL赋值给*r，起不到尾指针的作用。
	// LNode *s, *r = L;
	LNode *s, *r;

	// STEP: 声明一个整型变量x，用于接收用户输入。（以9999作为最后一个有效数据）
	int x;


	// NOTE: 初始化链表
	// STEP: 创建头结点，并用头指针L指向
	L = (LNode *) malloc(sizeof(LNode));
	L->next = NULL;

	// STEP: 初始化尾指针
	r = L;


	// NOTE: 尾插法，建立链表
	do {
		// STEP: 从标准输入读取用户输入
		printf("Please input: ");
		scanf("%d", &x);

		// STEP: 创建新节点
		// HINT: 申请一个新空间给s，强制类型转换为LNode类型
		s = (LNode *) malloc(sizeof(LNode));
		// HINT: 新结点中的数据，初始化为读取到的值
		s->data = x;
		// HINT: 新结点的指针域，初始化为空
		s->next = NULL;

		// STEP: 让新结点链接在表尾
		// HINT: 让尾指针所指结点（尾结点）的指针域，指向s指针所指结点始址
		r->next = s;

		// STEP: 更新尾指针r的指向。即：让r与s同指向即可实现r指向新表尾
		r = s;
	} while (x != 9999); // 直到用户输入9999为止
}


// FUNCTION: 按序号查找结点值
// @param: pos代表查找的结点位置
LNode *GetElem(LinkList L, int pos) {
	// NOTE: 变量声明——方便遍历
	// STEP: 引入计数变量i
	int i = 1;

	// STEP: 引入临时结构体指针变量p
	LNode *p = L->next;


	// NOTE: 特殊值处理
	// HINT: 当pos<0，不存在该类结点，返回NULL
	if (pos < 0) {
		return NULL;
	}

	// HINT: 当pos为0，认为需要返回头结点，返回L
	if (pos == 0) {
		return L;
	}


	// NOTE: 遍历链表，实现按序号查找
	// HINT: 当临时指针变量不空，且实际遍历位置i未达到目标位置pos，可继续遍历。
	//  万一链表已经完全遍历——p为空，但仍未找到目标位置结点，应返回NULL
	while (p && i < pos) {
		p = p->next;
		++i;
	}

	return p;
	// HINT: 没有必要用一下写法对于返回值进行处理！
	//  因为：如果所传入的pos超过了链表长度，那么”i < pos“一定得不到满足。不过，p的值在遍历链表的过程中，一定会变成NULL。于是，退出循环。
	//  故：没有必要如下处理！直接return p;即可
/*	if (i == pos) {
		return p;
	} else {
		return NULL;
	}*/
}


// FUNCTION: 按值查找
// @param: val代表需要查找的结点值
LNode *LocateElem(LinkList L, ElemType val) {
	// NOTE: 引入临时结构体指针变量p，并指向链表的第一个结点
	LNode *p = L->next;

	// NOTE: 遍历链表，查找期望的值
	while (p != NULL && p->data != val)
		p = p->next;

	return p;
}


// FUNCTION: 向第i个位置插入新结点
// @param: pos代表期望插入的元素位置；val代表期望插入的元素值
bool ListFrontInsert(LinkList &L, int pos, ElemType val) {
	// NOTE: 变量准备
	// STEP: 创建结点指针p，使之指向待插位置的前一个结点
	LNode *p = GetElem(L, pos - 1);

	// NOTE: 插入合法性检查
	if (NULL == p) {
		return false;
	}

	// NOTE: 执行插入操作
	// STEP: 新结点s初始化
	LNode *s = (LNode *) malloc(sizeof(LNode));
	s->data = val;
	s->next = NULL;

	// STEP: 将新结点s插入链表中
	s->next = p->next;
	p->next = s;

	return true;
}


// FUNCTION: 删除第i个结点
bool ListDelete(LinkList &L, int pos) {
	// NOTE: 变量准备
	// STEP: 创建结点指针p，使之指向待删结点的前一个结点
	LinkList p = GetElem(L, pos - 1);


	// NOTE: 删除合法性检查
	if (NULL == p) {
		return false;
	}


	// NOTE: 执行删除操作
	// STEP: 创建结点指针q，指向待删结点
	LinkList q = p->next;

	// STEP: 断链
	p->next = q->next;

	// STEP: 释放对应结点的空间
	free(q);

	return true;
}


// FUNCTION: 检查链表是否存在
bool isExist(LinkList L) {
	if (L == NULL) {
		return false;
	}

	return true;
}


// FUNCTION: 检查链表是否为空
bool isEmpty(LinkList L) {
	if (L->next == NULL) {
		printf("此链表为空链表！\n");

		return true;
	}

	return false;
}


// FUNCTION: 打印链表中每个结点的值
void PrintList(LinkList L) {
	// NOTE: 操作合法性检查
	// STEP: 检查链表是否存在
	if (!isExist(L)) {
		return;
	}

	// STEP: 检查链表是否为空
	if (isEmpty(L)) {
		return;
	}


	// NOTE: 遍历链表，打印输出
	// STEP: 头指针L指向头结点的后一个（有效）结点
	L = L->next;

	// STEP: 逐个节点遍历链表L，并输出
	while (L != NULL) {
		// 打印当前结点数据
		printf("%3d", L->data);
		// 指向下一个结点
		L = L->next;
	}
	printf("\n");
}


int main() {
	setbuf(stdout, NULL);

	// NOTE: Variable declaration
	// STEP: 定义链表头指针，是结构体指针类型
	LinkList L;

	int position;
	ElemType value;
	LinkList ret;

	// NOTE: Inputs
	// STEP: 以头插法向链表输入数据输入数据。9 5 2 7 9999
/*	CreatList_fromHead(L);
	printf("List sequence is : ");
	PrintList(L);*/

	// STEP: 以尾插法向链表输入数据输入数据。9 5 2 7 9999
	CreatList_fromTail(L);
	printf("List sequence is : ");
	PrintList(L);


	// NOTE: 按序号查找
/*
	printf("Query by position...\nPlease input your wanted position: ");
	scanf("%d", &position);

	// STEP: 后续处理
	if (ret != NULL) {
		printf("Query by position success!\n");
		printf("Result is %d\n", ret->data);
	} else {
		printf("Query by position failed!\n");
	}
*/


	// NOTE: 按值查找
/*
	printf("Query by position...\nPlease input your wanted value: ");
	scanf("%d", &value);
	// STEP: 调用函数，获取返回值
	ret = LocateElem(L, value);

	// STEP: 后续处理
	if (ret != NULL) {
		printf("Query by serial value success!\n");
		printf("%d\n", ret->data);
	} else {
		printf("Query by value failed!\n");
	}
*/


	// NOTE: 在第i个位置插入
/*
	printf("Insert your value at wanted position...\n");
	printf("Please input your wanted position: ");
	scanf("%d", &position);
	printf("Please input your wanted value: ");
	scanf("%d", &value);

	if (ListFrontInsert(L, position, value)) {
		printf("Insert operation success!\n");

		PrintList(L);
	} else {
		printf("Insert operation failed!\n");
	}
*/


	// NOTE: 删除第i个结点
/*
	printf("Delete wanted node...\n");
	printf("Please input your wanted position: ");
	scanf("%d", &position);

	if (ListDelete(L, position)) {
		printf("Delete operation success!\n");

		PrintList(L);
	} else {
		printf("Delete operation failed!\n");
	}
*/


	// NOTE: Outputs（链表打印）
	// PrintList(L);


	// NOTE: Ending
	return 0;
}


/*
 * REVIEW: 本代码仍有优化的空间。
 * 比方说，每次malloc内存申请，都要判断是否申请失败的问题。
 * */
